package leetcode_1201_1300;

import java.util.*;

public class LeeCode_1262 {
    public static void main(String[] args) {
        System.out.println(maxSumDivThree(new int[]{1,2,3,4,4}));
    }
    private static int maxSumDivThree(int[] nums) {
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        map.put(1, new PriorityQueue<>(Comparator.comparingInt(o -> o)));
        map.put(2, new PriorityQueue<>(Comparator.comparingInt(o -> o)));
        for (int num : nums) {
            int yu = num % 3;
            if (yu == 0){
                continue;
            }
            map.get(yu).add(num);
        }
        PriorityQueue<Integer> q1 = map.get(1);
        PriorityQueue<Integer> q2 = map.get(2);
        int sum = Arrays.stream(nums).sum();
        if (sum % 3 == 1){
            int t1 = Integer.MAX_VALUE, t2 = t1;
            if (q2.size() >= 2){
                t2 = q2.poll() + q2.poll();
            }
            if (q1.size() > 0){
                t1 = q1.poll();
            }
            sum -= Math.min(t1, t2);
        }else if (sum % 3 == 2){
            int t1 = Integer.MAX_VALUE, t2 = t1;
            if (q1.size() >= 2){
                t2 = q1.poll() + q1.poll();
            }
            if (q2.size() > 0){
                t1 = q2.poll();
            }
            sum -= Math.min(t1, t2);
        }
        return sum;
    }
}
